package main

import "fmt"

const (
	// 行
	RAW int = 4
	// 列
	COL int = 5
)

const boxMax = 4 //背包放的最大值

// 物品的重量 舍弃数组的0位置元素
var weight = [RAW]int{0, 1, 4, 2}

// 物品的价值 舍弃数组的0位置元素
var val = [RAW]int{0, 1500, 3000, 2000}

// 动态规划网格
var cells [RAW][COL]int

// 用于回溯选择的商品 selected[i]=1 表示放进背包，0表示不放进背包
var selected [RAW]int

// 动态规划计算网格
func dynamic() {
	for i := 1; i < len(val); i++ {
		for j := 1; j <= boxMax; j++ {
			cells[i][j] = maxValue(i, j)
		}
	}

	show()
	findBack2()

	fmt.Println("selected goods is ", selected)
}

// 判断当前单元格最大价值方法
// i 为顺序列表的大值
// j 为物品的重量的下标
func maxValue(i, j int) int {
	//当前商品不能放入背包
	if j < weight[i] {
		return cells[i-1][j]
	}

	// 可放进背包时候，计算放入当前商品后的最大价值
	curr := val[i] + cells[i-1][j-weight[i]]
	if curr >= cells[i-1][j] {
		return curr
	}

	return cells[i-1][j]
}

func show() {

	for i := 0; i < len(cells); i++ {

		for j := 0; j < len(cells[i]); j++ {
			fmt.Printf("%5d ", cells[i][j])
		}

		fmt.Println()

	}
}

// 回溯选择的商品方法
func findBack2() {
	col := boxMax
	for i := RAW - 1; i > 0; i-- {
		if cells[i][col] > cells[i-1][col] {
			selected[i] = 1
			fmt.Println(col)
			col = col - weight[i]

		} else {
			selected[i] = 0
		}
	}
}

func main() {
	fmt.Println("重量：", weight)
	fmt.Println("价值： ", val)

	dynamic()
}
